/**
 * 按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
 *
 * n皇后问题 研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 *
 * 给你一个整数 n ，返回所有不同的n皇后问题 的解决方案。
 *
 * 每一种解法包含一个不同的n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * 链接：https://leetcode.cn/problems/n-queens
 */
class SolveNQueens {
    List<List<String>> res=new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] chessboard=new char[n][n];
        for(char[] chess:chessboard) {
            Arrays.fill(chess,'.');
        }
        backTrack(n,0,chessboard);
        return res;
    }
    public void backTrack(int n,int row,char[][] chessboard) {
        if(row==n) {
            res.add(Array2List(chessboard));
        }
        for(int col=0;col<n;col++) {
            if(isVaild(row,col,n,chessboard)) {
                chessboard[row][col]='Q';
                backTrack(n,row+1,chessboard);
                chessboard[row][col]='.';
            }
        }
    }
    public List Array2List(char[][] chessboard) {
        List<String> ret=new ArrayList<>();
        for(char[] chess:chessboard) {
           ret.add(String.copyValueOf(chess));
        }
        return ret;
    }
    public boolean isVaild(int row,int col,int n,char[][] chessboard) {
        for(int i=0;i<n;i++) {
            if(chessboard[i][col]=='Q') {
                return false;
            }
        }
        for(int i=row-1,j=col-1;j>=0&&i>=0;i--,j--) {
            if(chessboard[i][j]=='Q') {
                return false;
            }
        }
        for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++) {
            if(chessboard[i][j]=='Q') {
                return false;
            }
        }
        return true;
    }

}